package com.lw.leetcode.binary.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1498. 满足条件的子序列数目
 * o
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/20 10:39
 */
public class NumSubseq {

    public static void main(String[] args) {
        NumSubseq test = new NumSubseq();

        // 4
        int[] arr = {3, 5, 6, 7};
        int t = 9;

        // 6
//        int[] arr = {3,3,6,8};
//        int t = 10;

        // 61
//        int[] arr = {2,3,3,4,6,7};
//        int t = 12;

        int i = test.numSubseq(arr, t);
        System.out.println(i);
    }

    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int length = nums.length;
        int end = length - 1;
        int count = find(nums, (target >> 1) + 1, 0, end);
        if (count == -1) {
            return 0;
        }
        long sum = count + 1L;
        count = find(nums, target - nums[0] + 1, 1, end);
        if (count == -1) {
            return (int) sum;
        }
        long[] items = new long[count + 1];
        items[1] = 1;
        long item = 1;
        for (int i = 1; i < count; i++) {
            item = (item << 1) % 1000000007;
            items[i + 1] = (items[i] + item) % 1000000007;
        }
        sum = (sum + items[count]) % 1000000007;
        end = count;
        for (int i = 1; i < length; i++) {
            count = find(nums, target - nums[i] + 1, i + 1, end);
            if (count == -1) {
                break;
            }
            sum = (sum + items[count - i]) % 1000000007;
            end = count;
        }
        return (int) sum;
    }

    private int find(int[] arr, int t, int st, int end) {
        if (st == arr.length || arr[st] >= t) {
            return -1;
        }
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (arr[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

}
